package cn.dai;

/**
 * @author ArkD42
 * @file 1 - Java基础语法
 * @create 2020 - 06 - 02 - 11:09
 */

import org.junit.Test;

/**
 * 稀疏数组
 * 当一个数组，大部分的元素为0或者相同的一个数值时，可以使用洗漱数组来保存这个数组
 *
 */
public class SparseArray {

    @Test
    public void sparse(){

        // 静态初始化
        int[][] arr = {
                {0,0,0,1,0,0,0,2,0},
                {1,0,0,2,0,7,0,0,0},
                {0,0,3,0,0,0,0,5,9}
        };

        // 动态初始化
        int[][] arr2 = new int[10][10];
        arr2[1][2] = 1;
        arr2[2][3] = 2;

        // 稀疏数组存储具有不同值的元素的值和索引位置
        // 在上面这个二维整形数组中，我们要做的是存储这个元素的行与列


        //打印查看
        printTwoDimensionalArrays(arr2);

        System.out.println("- - - - - - - - - -");

        printTwoDimensionalArrays(arr);

        System.out.println("- - - - - - - - - -");

        //调用稀疏数组
        printTwoDimensionalArrays(createSparseArray(arr));

        System.out.println("- - - - - - - - - -");

        printTwoDimensionalArrays(createSparseArray(arr2));

    }

    // 打印查看 封装成一个方法
    public void printTwoDimensionalArrays(int[][] tdArr){
        for (int[] row : tdArr){
            for (int element: row){
                System.out.printf("%d \t",element);
            }
            System.out.println();
        }
    }

    // 生成稀疏数组
    public int[][] createSparseArray(int[][] tdArr){
        int sum = 0;
        for (int i = 0;i < tdArr.length;i++){
            for (int j = 0; j <tdArr[i].length;j++){
                if (tdArr[i][j] != 0){
                    sum++;
                }
            }
        }

        //根据收集的非0元素，和我们的数组长度信息，创建稀疏数组
        int[][] sparseArray = new int[sum + 1][3];
        sparseArray[0][0]=tdArr.length;
        sparseArray[0][1]=tdArr[tdArr.length - 1].length;
        sparseArray[0][2]=sum;

        int count = 0; // 存储的非零元素个数的计数器
        for (int i = 0;i < tdArr.length;i++){
            for (int j = 0; j <tdArr[i].length;j++){
                if (tdArr[i][j] != 0){
                    count ++;
                    sparseArray[count][0] = i;
                    sparseArray[count][1] = j;
                    sparseArray[count][2] = tdArr[i][j];
                }
            }
        }

        return sparseArray;
    }

    // 用稀疏数组恢复成源数组
    public int[][] recoverOriginArray(int[][] sparseArray){

        int[][] originArray = new int[ sparseArray[0][0] ][ sparseArray[0][1] ];

        for (int i = 0; i <sparseArray.length ; i++) {
            originArray[ sparseArray[i][0] ][ sparseArray[i][1] ] = sparseArray[i][2];
        }
        return originArray;
    }
}
